import java.util.Arrays;

public class PriorityQueue {
    public int[] elem;
    public int usedSize;

    public PriorityQueue() {
        this.elem = new int[20];//初始容量
    }

    /**
     * 建堆的时间复杂度：
     *
     * @param array
     */
    public void createHeap(int[] array) {
        for (int i = 0; i < array.length; i++) {//把数组存入elem中
            this.elem[i] = array[i];
            this.usedSize++;
            if (isFull()) {//判断是否满了,需要扩容
                this.elem = Arrays.copyOf(elem,2*elem.length);
            }
        }
        for (int parent = (usedSize-1-1)/2; parent >= 0; parent--) {//从最后开始 让每一个父节点都进行调整
            //usedSize -1 是最后一个元素的下标
            //(元素下标-1)/2 是当前元素的父节点
            shiftDown(parent, usedSize);//对堆进行调整 下标范围: parent 到 usedSize
        }
    }

    /**
     *
     * @param parent 是每棵子树的根节点的下标
     * @param end  是每棵子树调整结束的结束条件
     * 向下调整的时间复杂度：O(logn)
     */
    private void shiftDown(int parent,int end) {//向下整理 大根堆
        int child = parent * 2 + 1;//从给的root(父节点) 找到左子节点
        while(child < end) {
            if (child + 1 < this.usedSize && this.elem[child] < this.elem[child+1]) {
                child++;//从当前兄弟节点中找到最大值
            }
            if (this.elem[child] > this.elem[parent]) {//子节点比父节点大时(不满足大根堆时)
                swap(child,parent);//交换

                parent = child;//让当前位置的子节点成为新的父节点 然后继续向下整理
                child = parent * 2 + 1;//找到新父节点的左子节点

            }else {
                break;
            }
        }
    }


    /**
     * 入队：仍然要保持是大根堆
     *
     */
    private void swap (int l,int r) {
        int cmp = this.elem[l];
        this.elem[l] = this.elem[r];
        this.elem[r] = cmp;
    }
    public void push(int val) {
        if (isFull()) {
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        this.elem[usedSize] = val;
        this.usedSize++;

        shiftUp(usedSize - 1);//向上进行调整

    }

    private void shiftUp(int child) {
        int parent = (child-1) / 2;
        while (child > 0) {//遍历到顶部结束
            if(elem[child] > elem[parent]) {
                swap(child,parent);
                child = parent;//让当前位置的父节点成为新的子节点 然后继续向上整理
                parent = (child-1)/2;//找到新子节点的父节点
            }else {
                break;
            }
        }
    }

    public boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    /**
     * 出队【删除】：每次删除的都是优先级高的元素
     * 仍然要保持是大根堆
     */
    public void pollHeap() {
        if (this.isEmpty()) {
            return;
        }
        this.swap(0,usedSize-1);//让顶部与尾部进行交换
        usedSize--;//从总数上进行删除
        this.shiftDown(0,usedSize);//向下调整(除了顶部外,其他满足条件,所以向下调整一遍即可)

    }

    public boolean isEmpty() {
        return this.usedSize == 0;
    }

    /**
     * 获取堆顶元素
     * @return
     */
    public int peekHeap() {//显示顶部
        return this.elem[0];
    }
}